1. Field of the Invention
The invention relates generally to method and apparatus carried out on a digital computer for converting a source program to an object code, and more particularly to an aliasing method and apparatus using alias lists for improving the efficiency of code optimization.
2. Description of the Prior Art
Aliasing in optimizing compilers is described in Aho, Sethi and Ullman, "Compilers: Principles, Techniques and Tools", Addison-Wesley (1986), Chpt. 10, pp. 585-722.
Other prior art examples include:
J Barth, "A Practical Interprocedural Data Flow Analysis Algorithm", CACM Vol. 21, No. 9, September 1978, pp. 724-736. PA1 A. J. Demers, A. Neirynck, P. Panagaden; "Computation of Aliases and Support Sets", ACM Symposium on Principles of Programming Languages, 1987, pp. 274-283. PA1 S. Horwitz, P. Pfeiffer, and T. Reps, "Dependence Analysis for Pointer Variables", SIGPLAN Conference on Programming Languages Design and Implementation, 1989, pp. 28-40. PA1 J. Larus and P. Hilfinger, "Detecting Conflicts Between Structure Access", SIGPLAN Conference on Programming Languages Design and Implementation, 1988, pp. 21-34. PA1 z=x+y; PA1 *q=exp1; PA1 w=x+y;
In general, if two or more expressions denote the same memory address, the expressions are aliases of one another. The presence of pointers and procedures in data flow analysis introduce aliases and complexity.
U.S. Pat. No. 5,107,418 describes a deficiency of the prior art in that optimizing compilers do not process loops that include procedure calls or de-references of pointers because these events must be treated as though they reference all variables in the program. Attempting to include procedure calls and de-references of pointers using the known techniques would result in a scalar data dependence graph that is slow to construct and too large for available memory. U.S. Pat. No. 5,107,418 discloses a method for representing scalar data dependencies for an optimizing compiler.
References to large structures, pointer de-references and procedure calls, along with debug, exception, and multi-tasking synchronization points, all have an effect on variables not directly referenced by the operation. At the point the operation is performed, optimization must be inhibited on expressions containing these indirectly referenced variables as operands. For example:
If the variable x happens to be an external variable, then there is a chance that the assignment using the pointer de-reference to q may modify the external variable x. Therefore, x+y will have to be evaluated twice rather than just once at the assignment to z, saving the result in a register to be later assigned to w.
A problem results when the number of indirectly referenced variables is very large. For example, an assignment to a pointer based variable such as *q can indirectly affect hundreds of external variables. If there are many pointer de-references or many of the other indirect effects, then optimization can spend a significant amount of time just updating its internal data structures to reflect the possible definitions or uses that are occurring.
Because this efficiency problem occurs most often due to constructs such as the pointer de-reference, it is basically an aliasing problem. The variables that share or potentially share the same space as a given variable are the variable's aliases.
It is desirable to provide enough flexibility to accommodate procedure calls and exception handling in an aliasing model and thereby solve the efficiency problem for those constructs also.
It would also be beneficial to have the flexibility to add compiler generated variables that are aliased to user variables to provide special views of user variables.